package P1线性结构.LeetCode单调栈;

import P1线性结构.LinkedList;

public class LeetCode316 {
    public String removeDuplicateLetters(String s) {
        //记录每一个字母的个数 (计数排序)
        int[] count = new int[26];  //0~'a' 1~'b' .... 25~'z'
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count[c - 'a']++;
        }
        //记录每一个字母的存在性
        boolean[] exits = new boolean[26];  //默认全部是false
        //构建一个单调递增栈
        //Java中LinkedList当栈用的话 栈顶在表头 不是在表尾！！！
        LinkedList<Character> stack = new LinkedList<>();

        for (Character c : s.toCharArray()) {
            //无论当前字母是否进栈 次数都要减一 已经处理过了
            count[c - 'a']--;
            if (exits[c - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && c < stack.peek()) {
                //如果字母唯一存在的 则不能弹
                if (count[stack.peek() - 'a'] == 0) {
                    break;
                }
                //后面还有该字母出现 则弹栈 将存在性变为false
                exits[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            //将存在性变为true
            exits[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (Character c : stack) {
            sb.append(c);
        }
        return sb.reverse().toString();
    }
}
